package com.fyt.recover.order;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class BucketSortIntVersion {

    public static void BucketSortIntVersion(int [] arr, int bucketSize){
      int max=  Arrays.stream(arr).max().getAsInt();
      //min还可以充当偏移量
      int min=  Arrays.stream(arr).min().getAsInt();



      //确定桶的数量
        int bucketCount=(max-min)/bucketSize+1;
     //初始化桶
        List<List<Integer>> buckets=new ArrayList<>(bucketCount);
        for (int i = 0; i <bucketCount ; i++) {
            buckets.add(new ArrayList<>());
        }
  //往桶里面放数据
        for (int i = 0; i <arr.length ; i++) {
          int index=  (arr[i]-min)/bucketSize;
          buckets.get(index).add(arr[i]);
        }
     //分别对每个桶进行排序
        for(List<Integer> bucket:buckets){
            Collections.sort(bucket);
        }
        //将排序后的元素放回原数组
        int index=0;
        for(List<Integer> bucket:buckets){
            for(int num:bucket){
                arr[index++]=num;
            }
        }

        System.out.println(Arrays.toString(arr));
    }
}
